TIP

插入排序（Insertion sort）是一种简单直观且稳定的排序算法。

如果有一个已经有序的数据序列，要求在这个已经排好的数据序列中插入一个数，但要求插入后此数据序列仍然有序，这个时候就要用到一种新的排序方法——插入排序法。

算法适用于少量数据的排序，时间复杂度O(n^2)。

private void insertSort(int[] arr) {
    for(int i = 1; i < arr.length; i ++) {
        for (int j = i; j > 0; j--) {
            if (arr[j] < arr[j - 1]) {
                int t = arr[j];
                arr[j] = arr[j - 1];
                arr[j - 1] = t;
            }
        }
    }
}

上面的代码更改良, 可以将条件放入到 for 循环中

private void insertSort(int[] arr) {
    for(int i = 1; i < arr.length; i ++) {
        for (int j = i; j > 0 && arr[j] < arr[j - 1]; j--) {
            int t = arr[j];
            arr[j] = arr[j - 1];
            arr[j - 1] = t;
        }
    }
}

但是上面的排序还是存在问题，因为每次都在进行交换元素，这样的元素之间的交换会带来很大的损耗，所以需要改良。

private void insertSort(int[] arr) {
    for(int i = 1; i < arr.length; i ++) {
        int e = arr[i];
        int j;
        for (j = i; j > 0 && arr[j - 1] > e; j--) {
            arr[j] = arr[j - 1];
        }
        arr[j] = e;
    }
}

TIP

从上面其实可以看出，插入排序和选择排序相比，插入排序可以提前退出，所以插入排序理论是要比选择排序更快的。